package doing;

import com.study.common.ListNode;
import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 328. Odd Even Linked List 奇偶链表
 * <p>
 * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，
 * 这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
 * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为
 * O(nodes)，nodes 为节点总数。
 * <p>
 * 示例 1:
 * 输入: 1->2->3->4->5->NULL
 * 输出: 1->3->5->2->4->NULL
 * <p>
 * 示例 2:
 * 输入: 2->1->3->5->6->4->7->NULL
 * 输出: 2->3->6->7->1->5->4->NULL
 * <p>
 * 2019-05-19 04:29
 **/
@SuppressWarnings("all")
public class OddEvenLinkedList {

    public ListNode oddEvenList(ListNode head) {
        // 190519 first
        if (head == null || head.next == null) {
            return head;
        }
        // head 为奇链表头结点，o 为奇链表尾节点
        ListNode o = head;

        // p 为偶链表头结点
        ListNode p = head.next;

        // e 为偶链表尾节点
        ListNode e = p;
        while (o.next != null && e.next != null) {
            o.next = e.next;
            o = o.next;

            e.next = o.next;
            e = e.next;
        }
        o.next = p;
        return head;
    }

    @Test
    public void test() {
        info(oddEvenList(new ListNode(3, 1, 2, 5, 12, 1, 3, 1, 123, 1132, 1)));
    }
}




























/*
public ListNode oddEvenList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    // head 为奇链表头结点，o 为奇链表尾节点
    ListNode o = head;

    // p 为偶链表头结点
    ListNode p = head.next;

    // e 为偶链表尾节点
    ListNode e = p;
    while (o.next != null && e.next != null) {
        o.next = e.next;
        o = o.next;
        e.next = o.next;
        e = e.next;
    }
    o.next = p;
    return head;
}
*/